#include <bits/stdc++.h>
using namespace std;
int n;
bool check1(int n){
    int a=int(sqrt(n));
    return a*a==n;
}
bool check2(int n){
    for(int i=1;i*i<=n;i++){
        if(check1(n-i*i)){
            return true;
        }
    }
    return false;
}
bool check3(int n){
    for(int i=1;i*i<=n;i++){
        if(check2(n-i*i)){
            return true;
        }
    }
    return false;
}
int main(void){
    while(~scanf("%d",&n) && n!=-1){
        if(check1(n)){
            printf("1\n");
        }
        else if(check2(n)){
            printf("2\n");
        }
        else if(check3(n)){
            printf("3\n");
        }
        else{
            printf("4\n");
        }
    }
    return 0;
}